// -*- coding: utf-8 -*-
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-12 22:37
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.DataStruct.Tree.Trie;

import java.util.*;

@SuppressWarnings("ALL")
public class Trie {
    /**
     * 创建节点
     */
    class TriedNode {
        boolean end;
        TriedNode[] tns = new TriedNode[26];
    }

    TriedNode root;

    public Trie() {
        root = new TriedNode();
    }

    public void insert(String word) {
        TriedNode p = root;
        for (int i = 0; i < word.length(); i++) {
            int u = word.charAt(i) - 'a';
            if (p.tns[u] == null) {
                p.tns[u] = new TriedNode();
            }
            p = p.tns[u];
        }
        p.end = true;
    }

    public boolean search(String word) {
        TriedNode p = root;
        for (int i = 0; i < word.length(); i++) {
            int u = word.charAt(i) - 'a';
            if (p.tns[u] == null) {
                return false;
            }
            p = p.tns[u];
        }
        return p.end;
    }

    public boolean startsWith(String prefix) {
        TriedNode p = root;
        for (int i = 0; i < prefix.length(); i++) {
            int c = prefix.charAt(i) - 'a';
            if (p.tns[c] == null) {
                return false;
            }
            p = p.tns[c];
        }
        return true;
    }

}
//    /**
//     * 使用二位数组创建字典树(前缀树)
//     */
//    int N = 1_0_009;
//    int[][] trie;
//    // 使用count标记以当前字符结束字符的次数
//    int[] count;
//    // index记录了当前使用了多少个各自 -> 未使用的格子中的数字应该为0
//    int index;
//
//
//    /**
//     * 字典树初始化
//     * 每一级代表单词的第几位
//     */
//    public Trie() {
//        trie = new int[N][26];
//        count = new int[N];
//        index = 0;
//    }
//
//    public void insert(String word) {
//        int p = 0;
//        for (int i = 0; i < word.length(); i++) {
//            int u = word.charAt(i) - 'a';
//            if (trie[p][u] == 0) {
//                trie[p][u] = ++index;
//            }
//            p = trie[p][u];
//        }
//        count[p]++;
//    }
//
//    public boolean search(String word) {
//        int p = 0;
//        for (int i = 0; i < word.length(); i++) {
//            int c = word.charAt(i) - 'a';
//            if (trie[p][c] == 0) {
//                return false;
//            }
//            p = trie[p][c];
//        }
//        // 当前级存在单词
//        return count[p] != 0;
//    }
//
//    public boolean startsWith(String prefix) {
//        int p = 0;
//        for (int i = 0; i < prefix.length(); i++) {
//            int c = prefix.charAt(i) - 'a';
//            if (trie[p][c] == 0) {
//                return false;
//            }
//            p = trie[p][c];
//        }
//        // 当前级存在单词
//        return true;
//    }
//}

//    /**
//     * 字段声明:
//     * isStr: 判断当前节点是否是单词结尾（Trie是否访问过相同的字符）
//     * children: 多叉树的孩子节点表示
//     * c : 当前节点存储的字符
//     * Trie: 根节点不存储字符信息
//     */
//    Boolean isStr;
//    Map<Character, Trie> children = new HashMap<>();
//    Character c;
//
//    public Boolean getStr() {
//        return isStr;
//    }
//
//    public Map<Character, Trie> getChildren() {
//        return children;
//    }
//
//    public Character getC() {
//        return c;
//    }
//
//    public void setStr(Boolean str) {
//        isStr = str;
//    }
//
//    public void setChildren(Map<Character, Trie> children) {
//        this.children = children;
//    }
//
//    public void setC(Character c) {
//        this.c = c;
//    }
//
//    /**
//     * 构造器: 构造根节点
//     */
//    public Trie() {
//
//    }
//
//    public Trie(Character c) {
//        this.c = c;
//    }
//
//    /**
//     * 单词结尾构造方法
//     */
//
//    public Trie constructTrie(Boolean isStr, Character c) {
//        Trie trie = new Trie();
//        trie.isStr = isStr;
//        trie.c = c;
//        return trie;
//    }
//
//    /**
//     * 插入元素
//     *
//     * @param word 插入字符串 -> 单词结束的时候需要将对应结束字符节点的Boolean记录为True表示Trie树遍历过该单词
//     */
//    public void insert(String word) {
//        int n = word.length();
//        if (n == 0) {
//            // 传入的字符串是空串
//            return;
//        }
//        Character val = word.charAt(0);
//        if (!children.containsKey(val)) {
//            // 孩子节点中不存在该前缀字符
//            if (n == 1) {
//                // 传入的字符串只有一个字符，达到字符串结尾位置
//                children.put(val, constructTrie(true, val));
//                return;
//            } else {
//                children.put(val, constructTrie(false, val));
//                // 继续添加字串
//            }
//        }
//        if (n > 1) {
//            children.get(val).insert(word.substring(1, n));
//        } else {
//            // 字符串结尾，做标记
//            children.get(val).setStr(true);
//        }
//
//    }
//
//
//    /**
//     * 寻找字符串
//     *
//     * @param word 查找单词
//     * @return 树中是否存在单词
//     */
//    public boolean search(String word) {
//        // 断言：传入的字符串不能为空
//        assert word != null && word.length() != 0 : "传入的字符串不能为空";
//        int n = word.length();
//        if (!this.children.containsKey(word.charAt(0))) {
//            // 不存在当前字符串的公共前缀
//            return false;
//        } else {
//            // 存在当前字符串的公共前缀
//            if (n > 1) {
//                return this.children.get(word.charAt(0)).search(word.substring(1, n));
//            }
//            // "abbbcd" && "abbb" , When the char in the 'b' and there have children of the trie Tree,in this time
//            // isStr is identified that the Trie Tree if have been searched the String as same as String
//            return this.getChildren().get(word.charAt(0)).isStr;
//        }
//    }
//
//    /**
//     * 判断树中是否存在以当前字符为前缀的字符串
//     *
//     * @param prefix 字符前缀
//     * @return 返回
//     */
//    public boolean startsWith(String prefix) {
//        // 断言：传入的字符串不能为空
//        assert prefix != null && prefix.length() != 0 : "传入的字符串不能为空";
//        int n = prefix.length();
//        if (!this.children.containsKey(prefix.charAt(0))) {
//            // 不存在当前字符串的公共前缀
//            return false;
//        } else {
//            // 存在当前字符串的公共前缀
//            if (n > 1) {
//                return this.children.get(prefix.charAt(0)).startsWith(prefix.substring(1, n));
//            }
//            // "abbbcd" && "abbb" , When the char in the 'b' and there have children of the trie Tree,in this time
//            // isStr is identified that the Trie Tree if have been searched the String as same as String
//            return true;
//        }
//    }


